package com.kaifamiao.deno;

import java.util.Arrays;

/**
 *
 */
public class Demo01 {


    public static void main(String[] args) {
        int[] nums = {9, 1, 4, 2, 6, 8, 3, 5};
        quickSort(nums, 0, nums.length - 1);

        System.out.println(Arrays.toString(nums));
    }

    private static void quickSort(int[] nums, int left, int right) {
        if (left > right){
            return;
        }
        int i = left;
        int j = right;

        // 基准值
        int num = nums[left];

        while(i < j){
            // 从右边开始找比 基准值小的 数的下标
            while (nums[j] >= num && i < j){
                j --;
            }
            // 循环结束条件： 1. j现在的位置是比 基准值小的数  2. i = j

            while (nums[i] <= num && i < j){
                i ++;
            }
            // 循环结束条件： 1. i现在的位置是比 基准值大的数  2. i = j

            // 交换 i 和 j 位置上的数
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }

        // 将 基准值 换到 中间去  i 一定等于 j
        nums[left] = nums[i];
        nums[i] = num;

        // 对基准值左边的数组元素进行 快排
        quickSort(nums, left, i - 1);

        // 对基准值右边的数组进行 快排
        quickSort(nums, i + 1, right);

    }
}
